1. Field of the Invention
This invention relates to packet networks with variable bit rate attributes. Specifically, the invention relates to packet networks that can transfer variable length packets, including frame relay service or ATM (Asynchronous Transfer Mode) and other fixed length packets (cells) at variable bit rates; to a method for avoiding congestion in packet networks; and to the node configurations required for these purposes.
2. Description of the Related Art
Hitherto, the transmission bit rate in a transmission line, for example, the transmission bit rate expressed in terms of bit/sec, has taken the form of a constant base rate. Similarly, switching facilities have operated at a constant base rate.
In packet networks or ATM networks, variable length packets or ATM-type fixed length packets (cells) are transferred through the network from source nodes to destination nodes via intermediate nodes. The packets are transferred on the basis of a destination address, or path or channel identifiers, corresponding to these packets. The network is constituted in such a manner that transmission is possible at user-convenient timings. These packet networks or ATM networks are constituted so that the average bit rate can vary in agreement with a users' convenience.
The following methods have been adopted as countermeasures against packet congestion in such networks.
The first system considered is a system where data transfer within the network is carried out on the basis of call admission control. Whenever packet congestion occurs, transmission from any terminal node where there is a new transmission request becomes impossible. In this case, another transmission request is made after a time, and if the congestion has cleared, the request is accepted and transmission becomes possible. In this particular case, even if congestion has occurred, transmission is still possible from terminals transmitting prior to the occurrence of the congestion. Therefore call acceptance control is not straightforward or entirely equitable.
Next, in a packet network, all terminal nodes can forward packets even if there is congestion. However, due to the congestion, overflow packets are discarded. Source nodes are notified that packets have been discarded, and re-transmission takes place. Thus, actual transmission is impossible.
The following method is employed in packet networks to cope with congestion. When packet congestion is detected, transmission restrictions are applied to the source nodes and their transmission is thereby suspended. The principles of congestion avoidance according to this method are illustrated in FIGS. 1A to 1C. FIGS. 1A to 1C show transmission of packets from a source node being suspended by means of a congestion notification from a destination (or intermediate) node.
A problem encountered with this method is that packets will be discarded when buffers in the terminal nodes have small capacity. Furthermore, transmission downtime lengthens when small capacity buffers are provided. Large-capacity buffers are needed to achieve efficient network operation, but this will result in overall network efficiency deteriorating and an increase in overall system costs. One way of ensuring that congestion does not occur would be to construct a network with plenty of surplus capacity. However, constructing a network with plenty of surplus capacity amounts to providing equipment that is used only on occasion; for example, buffers of sufficient size at intermediate and terminal nodes. This approach causes efficiency to deteriorate.
Another method for controlling congestion in packet networks is to control packet transfer by monitoring packet flow (by sampling short periods during packet transfer) and on this basis decide whether or not congestion is occurring (this is called window flow control). This technique is described in Japanese Unexamined Patent Disclosure No. 3-174848 (patent application Ser. No. 07/400,858, now issued as U.S. Pat. No. 5,193,151). The principles of congestion avoidance according to this method are shown in FIGS. 2A to 2C. According to this method, round-trip delay time is measured at source nodes. When the round-trip delay time decreases, it is estimated that the network is not in an overload condition. Thus, packet transfer from the source side is allowed to increase. On the other hand, if the round-trip delay time increases, it is estimated that the network is in an overload condition. Thus, packet transfer from the source side is decreased, halting the transfer of packets.
A problem encountered with window flow control is that packets are discarded when small capacity buffers are provided at the nodes. Moreover, the prediction of network congestion on the basis of delay times does not always agree with the actual condition of the network.
Because conventional detection of congestion amounts to detecting congestion after a state of congestion has already arisen, congestion is not prevented. In other words, conventional methods do not predict congestion of packet transmission at a future point in time on the basis of packet transfer rate at the present point of time.
In addition, conventional detection of the packet transfer rate for purposes of congestion detection does so based on a probability distribution model for traffic sources. Therefore, when packets from a large number of signal sources are multiplexed, conventional methods cannot cope with a case where signal source parameters change with time. Accordingly, because it has not predicted the packet transfer rate at a prescribed time in the future, it has not detect that congestion will occur.